package tree;

import offer.TreeNode;

/**
 * 根据一棵树的中序遍历与后序遍历构造二叉树。
 *
 * 注意:
 * 你可以假设树中没有重复的元素。
 *
 * 例如，给出
 *
 * 中序遍历 inorder =[9,3,15,20,7]
 * 后序遍历 postorder = [9,15,7,20,3]
 * 返回如下的二叉树：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 */
public class leetCode106_buildTree {


    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder,0, inorder.length - 1, postorder,0, postorder.length - 1);
    }

    public TreeNode build(int[] inorderr, int startIn, int endIn,
                          int[] postorder,int startPost,int endPost){
        if(startIn > endIn){
            return null;
        }

        int rootValue = postorder[endPost];
        TreeNode treeNode = new TreeNode(rootValue);
        int rootIndex = -1;
        for (int i = startIn; i <= endIn; i++) {
            if(inorderr[i] == rootValue){
                rootIndex = i;
            }
        }
        int lengthLeft = rootIndex - startIn;

        TreeNode left = build(inorderr,startIn,rootIndex - 1,
                postorder,startPost,startPost + lengthLeft -1);

        TreeNode right =build(inorderr,rootIndex + 1,endIn,
                postorder,startPost + lengthLeft,endPost - 1);

        treeNode.left = left;
        treeNode.right = right;
        return treeNode;


    }

    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        return build2(inorder,0,inorder.length - 1,
                postorder,0,postorder.length - 1);
    }

    public TreeNode build2(int[] inorder,int inStart,int inEnd,
                           int[] postorder, int postStart, int postEnd){
        if(inStart > inEnd){
            return null;
        }

        TreeNode root = new TreeNode(postorder[postEnd]);
        int inRootIndex = -1;
        for (int i = inStart; i <= inEnd ; i++) {
            if(inorder[i] == postorder[postEnd]){
                inRootIndex = i;
                break;
            }
        }
        int leftSize = inRootIndex - inStart;

        TreeNode left = build2(inorder,inStart,inRootIndex - 1,
                                postorder,postStart,postStart + leftSize - 1);
        TreeNode right = build2(inorder,inRootIndex + 1,inEnd,
                                postorder,postStart + leftSize,postEnd - 1);
        root.left = left;
        root.right = right;

        return root;

    }
    
}
